@testset "Static graphs" begin
    @testset "DiGraphs" begin
        g = @inferred(SG.complete_digraph(5))
        @test nv(g) == 5 && ne(g) == 20
        @test isvalid_simplegraph(g)
        # tests for extreme values
        g = SG.complete_digraph(0)
        @test nv(g) == 0 && ne(g) == 0
        g = SG.complete_digraph(1)
        @test nv(g) == 1 && ne(g) == 0
        g = SG.complete_digraph(2)
        @test nv(g) == 2 && ne(g) == 2
        g = @inferred SG.complete_digraph(Int8(127))
        @test nv(g) == 127 && ne(g) == 127 * (127 - 1)
        @test eltype(g) == Int8
    end

    @testset "Graphs" begin
        g = @inferred(SG.complete_graph(5))
        @test nv(g) == 5 && ne(g) == 10
        @test isvalid_simplegraph(g)
        # tests for extreme values
        g = SG.complete_graph(0)
        @test nv(g) == 0 && ne(g) == 0
        g = SG.complete_graph(1)
        @test nv(g) == 1 && ne(g) == 0
        g = SG.complete_graph(2)
        @test nv(g) == 2 && ne(g) == 1
        g = @inferred SG.complete_graph(Int8(127))
        @test nv(g) == 127 && ne(g) == 127 * (127 - 1) ÷ 2
        @test eltype(g) == Int8
    end


    @testset "Bipartite Graphs" begin
        g = @inferred(SG.complete_bipartite_graph(5, 8))
        @test nv(g) == 13 && ne(g) == 40
        @test isvalid_simplegraph(g)
        # tests for extreme values
        g = SG.complete_bipartite_graph(0,0)
        @test nv(g) == 0 && ne(g) == 0
        g = SG.complete_bipartite_graph(5,0)
        @test nv(g) == 5 && ne(g) == 0
        g = SG.complete_bipartite_graph(0,5)
        @test nv(g) == 5 && ne(g) == 0
        g = @inferred SG.complete_bipartite_graph(Int8(100), Int8(27))
        @test nv(g) == 127 && ne(g) == 100 * 27
        @test eltype(g) == Int8
        g = SG.complete_bipartite_graph(Int8(127), Int8(0))
        @test nv(g) == 127 && ne(g) == 0
        g = SG.complete_bipartite_graph(Int8(0), Int8(127))
        @test nv(g) == 127 && ne(g) == 0
    end

    function iscompletemultipartite(g, partitions)
        sum(partitions) != nv(g) && return false
        n = nv(g)

        edges = 0
        for p in partitions
            edges += p*(Int(n)-p)
        end
        edges = div(edges, 2)

        edges != ne(g) && return false

        cur = 1
        for p in partitions
            currange = cur:(cur+p-1)
            lowerrange = 1:(cur-1)
            upperrange = (cur+p):n
            for u in currange
                for v in currange # check that no vertices are connected to vertices in the same partition
                    has_edge(g, u, v) && return false
                end

                for v in lowerrange # check all lower partition vertices
                    !has_edge(g, u, v) && return false
                end

                for v in upperrange # check all higher partition vertices
                    !has_edge(g, u, v) && return false
                end
            end
            cur += p
        end
        return true
    end

    @testset "Multipartite Graphs" begin
        g = @inferred(SG.complete_multipartite_graph([5, 8, 3]))
        @test nv(g) == 16 && ne(g) == 79
        @test isvalid_simplegraph(g)
        @test iscompletemultipartite(g, [5, 8, 3])
        # tests for extreme values
        g = SG.complete_multipartite_graph([0, 0, 0])
        @test nv(g) == 0 && ne(g) == 0
        g = SG.complete_multipartite_graph(Int[])
        @test nv(g) == 0 && ne(g) == 0
        g = SG.complete_multipartite_graph([5, 0, 3])
        @test nv(g) == 8 && ne(g) == 15
        @test iscompletemultipartite(g, [5, 0, 3])
        g = SG.complete_multipartite_graph(Int8[100, 25, 2])
        @test nv(g) == 127 && ne(g) == 2750
        @test eltype(g) == Int8
        @test iscompletemultipartite(g, [100, 25, 2])
        g = SG.complete_multipartite_graph([0, 10, 0, 2, 0, 3, 0, 0, 6, 0])
        @test nv(g) == 21 && ne(g) == 146
        @test iscompletemultipartite(g, [0, 10, 0, 2, 0, 3, 0, 0, 6, 0])
        g = SG.complete_multipartite_graph([5, 3, -1])
        @test nv(g) == 0 && ne(g) == 0
        g = SG.complete_multipartite_graph([-5, 0, -11])
        @test nv(g) == 0 && ne(g) == 0
        g = SG.complete_multipartite_graph([5, 3])
        h = SG.complete_multipartite_graph([5, 0, 3])
        j = SG.complete_multipartite_graph([0, 5, 0, 3, 0, 0])
        @test g == h == j
        @test_throws InexactError SG.complete_multipartite_graph(Int8[100, 20, 20])
    end

    function retrievepartitions(n, r)
        partitions = partitions = Vector{Int}(undef, r)
        c = cld(n,r)
        f = fld(n,r)
        for i in 1:(n%r)
            partitions[i] = c
        end
        for i in ((n%r)+1):r
            partitions[i] = f
        end
        return partitions
    end

    @testset "Turan Graphs" begin
        g = @inferred(SG.turan_graph(13, 4))
        @test nv(g) == 13 && ne(g) == 63
        @test isvalid_simplegraph(g)
        @test iscompletemultipartite(g, retrievepartitions(13, 4))
        # testing smaller int types
        g = SG.turan_graph(Int8(11), Int8(6))
        @test nv(g) == 11 && ne(g) == 50
        @test iscompletemultipartite(g, retrievepartitions(11, 6))
        g = SG.turan_graph(Int16(35), Int16(17))
        @test nv(g) == 35 && ne(g) == 576
        @test iscompletemultipartite(g, retrievepartitions(35, 17))
        # tests for extreme values
        g = SG.turan_graph(15,15)
        @test nv(g) == 15 && ne(g) == 105
        @test iscompletemultipartite(g, retrievepartitions(15, 15))
        g = SG.turan_graph(10, 1)
        @test nv(g) == 10 && ne(g) == 0
        @test iscompletemultipartite(g, retrievepartitions(10, 1))
        @test_throws DomainError SG.turan_graph(3,0)
        @test_throws DomainError SG.turan_graph(0,4)
        @test_throws DomainError SG.turan_graph(3,4)
        @test_throws DomainError SG.turan_graph(-1,5)
        @test_throws DomainError SG.turan_graph(3,-6)
    end

    @testset "Star Graphs" begin
        g = @inferred(SG.star_graph(5))
        @test nv(g) == 5 && ne(g) == 4
        @test isvalid_simplegraph(g)
        # tests for extreme values
        g = SG.star_graph(0)
        @test nv(g) == 0 && ne(g) == 0
        g = SG.star_graph(1)
        @test nv(g) == 1 && ne(g) == 0
        g = SG.star_graph(2)
        @test nv(g) == 2 && ne(g) == 1
        g = @inferred SG.star_graph(Int8(127))
        @test nv(g) == 127 && ne(g) == 127 - 1
        @test eltype(g) == Int8
    end

    @testset "Star DiGraphs" begin
        g = @inferred(SG.star_digraph(5))
        @test nv(g) == 5 && ne(g) == 4
        @test isvalid_simplegraph(g)
        # tests for extreme values
        g = SG.star_digraph(0)
        @test nv(g) == 0 && ne(g) == 0
        g = SG.star_digraph(1)
        @test nv(g) == 1 && ne(g) == 0
        g = SG.star_digraph(2)
        @test nv(g) == 2 && ne(g) == 1
        @test first(edges(g)) == SG.SimpleEdge(1, 2) # edges should point outwards from vertex 1
        g = @inferred SG.star_digraph(Int8(127))
        @test nv(g) == 127 && ne(g) == 127 - 1
        @test eltype(g) == Int8
    end

    @testset "Path DiGraphs" begin
        g = @inferred(SG.path_digraph(5))
        @test nv(g) == 5 && ne(g) == 4
        @test isvalid_simplegraph(g)
        # tests for extreme values
        g = SG.path_digraph(0)
        @test nv(g) == 0 && ne(g) == 0
        g = SG.path_digraph(1)
        @test nv(g) == 1 && ne(g) == 0
        g = @inferred SG.path_digraph(Int8(127))
        @test nv(g) == 127 && ne(g) == 126
        @test eltype(g) == Int8
    end

    @testset "Path Graphs" begin
        g = @inferred(SG.path_graph(5))
        @test nv(g) == 5 && ne(g) == 4
        @test isvalid_simplegraph(g)
        # tests for extreme values
        g = SG.path_graph(0)
        @test nv(g) == 0 && ne(g) == 0
        g = SG.path_graph(1)
        @test nv(g) == 1 && ne(g) == 0
        g = @inferred SG.path_graph(Int8(127))
        @test nv(g) == 127 && ne(g) == 126
        @test eltype(g) == Int8
    end

    @testset "Cycle DiGraphs" begin
        g = @inferred(SG.cycle_digraph(5))
        @test nv(g) == 5 && ne(g) == 5
        @test isvalid_simplegraph(g)
         # tests for extreme values
        g = SG.cycle_digraph(0)
        @test nv(g) == 0 && ne(g) == 0
        g = SG.cycle_digraph(1)
        @test nv(g) == 1 && ne(g) == 0
        g = SG.cycle_digraph(2)
        @test nv(g) == 2 && ne(g) == 2
        g = @inferred SG.cycle_digraph(Int8(127))
        @test nv(g) == 127 && ne(g) == 127
        @test eltype(g) == Int8
    end

    @testset "Cycle Graphs" begin
        g = @inferred(SG.cycle_graph(5))
        @test nv(g) == 5 && ne(g) == 5
        @test isvalid_simplegraph(g)
         # tests for extreme values
        g = SG.cycle_graph(0)
        @test nv(g) == 0 && ne(g) == 0
        g = SG.cycle_graph(1)
        @test nv(g) == 1 && ne(g) == 0
        g = SG.cycle_graph(2)
        @test nv(g) == 2 && ne(g) == 1
        g = @inferred SG.cycle_graph(Int8(127))
        @test nv(g) == 127 && ne(g) == 127
        @test eltype(g) == Int8
    end

    @testset "Wheel DiGraphs" begin
        g = @inferred(SG.wheel_digraph(5))
        @test nv(g) == 5 && ne(g) == 8
        @test isvalid_simplegraph(g)
          # tests for extreme values
        g = SG.wheel_digraph(0)
        @test nv(g) == 0 && ne(g) == 0
        g = SG.wheel_digraph(1)
        @test nv(g) == 1 && ne(g) == 0
        g = SG.wheel_digraph(2)
        @test nv(g) == 2 && ne(g) == 1
        g = SG.wheel_digraph(3)
        @test nv(g) == 3 && ne(g) == 4
        g = @inferred SG.wheel_digraph(Int8(127))
        @test nv(g) == 127 && ne(g) == 2 * 126
        @test eltype(g) == Int8
    end

    @testset "Wheel Graphs" begin
        g = @inferred(SG.wheel_graph(5))
        @test nv(g) == 5 && ne(g) == 8
        @test isvalid_simplegraph(g)
          # tests for extreme values
        g = SG.wheel_graph(0)
        @test nv(g) == 0 && ne(g) == 0
        g = SG.wheel_graph(1)
        @test nv(g) == 1 && ne(g) == 0
        g = SG.wheel_graph(2)
        @test nv(g) == 2 && ne(g) == 1
        g = SG.wheel_graph(3)
        @test nv(g) == 3 && ne(g) == 3
        g = @inferred SG.wheel_graph(Int8(127))
        @test nv(g) == 127 && ne(g) == 2 * 126
        @test eltype(g) == Int8
    end

    @testset "grids" begin
        g = @inferred(SG.grid([3, 3, 4]))
        @test nv(g) == 3 * 3 * 4
        @test ne(g) == 75
        @test Δ(g) == 6
        @test δ(g) == 3
        @test isvalid_simplegraph(g)

        g2 = @inferred(SG.grid((3, 3, 4)))
        @test g2 == g

        g = @inferred(SG.grid([3, 3, 4], periodic=true))
        @test nv(g) == 3 * 3 * 4
        @test ne(g) == 108
        @test Δ(g) == 6
        @test δ(g) == 6
        @test isvalid_simplegraph(g)

        g2 = @inferred(SG.grid((3, 3, 4), periodic=true))
        @test g2 == g
    end

    @testset "Clique Graphs" begin
        g = @inferred(SG.clique_graph(3, 5))
        @test nv(g) == 15 && ne(g) == 20
        @test g[1:3] == SG.complete_graph(3)
        @test isvalid_simplegraph(g)
    end

    @testset "Binary Trees" begin
        g = @inferred(SG.crosspath(3, SG.binary_tree(2)))
        # f = Vector{Vector{Int}}[[2 3 4];
        # [1 5];
        # [1 6];
        # [1 5 6 7];
        # [2 4 8];
        # [3 4 9];
        # [4 8 9];
        # [5 7];
        # [6 7]
        # ]
        I = [1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 9, 9]
        J = [2, 3, 4, 1, 5, 1, 6, 1, 5, 6, 7, 2, 4, 8, 3, 4, 9, 4, 8, 9, 5, 7, 6, 7]
        V = ones(Int, length(I))
        Adj = sparse(I, J, V)
        @test Adj == sparse(g)
        @test isvalid_simplegraph(g)
        @test_throws DomainError SG.binary_tree(Int8(8))

        g = @inferred(SG.double_binary_tree(3))
        # [[3, 2, 8]
        # [4, 1, 5]
        # [1, 6, 7]
        # [2]
        # [2]
        # [3]
        # [3]
        # [10, 9, 1]
        # [11, 8, 12]
        # [8, 13, 14]
        # [9]
        # [9]
        # [10]
        # [10]]
        I = [1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 5, 6, 7, 8, 8, 8, 9, 9, 9, 10, 10, 10, 11, 12, 13, 14]
        J = [3, 2, 8, 4, 1, 5, 1, 6, 7, 2, 2, 3, 3, 10, 9, 1, 11, 8, 12, 8, 13, 14, 9, 9, 10, 10]
        V = ones(Int, length(I))
        Adj = sparse(I, J, V)
        @test Adj == sparse(g)
        @test isvalid_simplegraph(g)
    end

    @testset "Roach Graphs" begin
        rg3 = @inferred(SG.roach_graph(3))
        # [3]
        # [4]
        # [1, 5]
        # [2, 6]
        # [3, 7]
        # [4, 8]
        # [9, 8, 5]
        # [10, 7, 6]
        # [11, 10, 7]
        # [8, 9, 12]
        # [9, 12]
        # [10, 11]
        I = [1, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9, 10, 10, 10, 11, 11, 12, 12]
        J = [3, 4, 1, 5, 2, 6, 3, 7, 4, 8, 9, 8, 5, 10, 7, 6, 11, 10, 7, 8, 9, 12, 9, 12, 10, 11]
        V = ones(Int, length(I))
        Adj = sparse(I, J, V)
        @test Adj == sparse(rg3)
        @test isvalid_simplegraph(rg3)
    end

    function isladdergraph(g)
        n = nv(g)÷2
        !(degree(g, 1) == degree(g, n) == degree(g, n+1) == degree(g, 2*n) == 2) && return false
        !(has_edge(g, 1, n+1) && has_edge(g, n, 2*n)) && return false
        !(has_edge(g, 1, 2) && has_edge(g, n, n-1) && has_edge(g, n+1, n+2) && has_edge(g, 2*n, 2*n-1) ) && return false
        for i in 2:(n-1)
            !(degree(g, i) == 3 && degree(g, n+i) == 3) && return false
            !(has_edge(g, i, i%n +1) && has_edge(g, i, i+n)) && return false
            !(has_edge(g, n+i,n+(i%n +1)) && has_edge(g, n+i, i)) && return false
        end
        return true
    end

    @testset "Ladder Graphs" begin
        g = @inferred(SG.ladder_graph(5))
        @test nv(g) == 10 && ne(g) == 13
        @test isvalid_simplegraph(g)
        @test isladdergraph(g)
        # tests for extreme values
        g = SG.ladder_graph(0)
        @test nv(g) == 0 && ne(g) == 0
        g = SG.ladder_graph(1)
        @test nv(g) == 2 && ne(g) == 1
        g = @inferred SG.ladder_graph(-1)
        @test nv(g) == 0 && ne(g) == 0
        g = SG.ladder_graph(Int8(63))
        @test nv(g) == 126 && ne(g) == 187
        @test eltype(g) == Int8
        @test isladdergraph(g)
        # tests for errors
        @test_throws InexactError SG.ladder_graph(Int8(64))
    end

    function iscircularladdergraph(g)
        n = nv(g) ÷ 2
        for i in 1:n
            !(degree(g, i) == 3 && degree(g, n+i) == 3) && return false
            !(has_edge(g, i, i%n +1) && has_edge(g, i, i+n)) && return false
            !(has_edge(g, n+i,n+(i%n +1)) && has_edge(g, n+i, i)) && return false
        end
        return true
    end

    @testset "Circular Ladder Graphs" begin
        g = @inferred(SG.circular_ladder_graph(5))
        @test nv(g) == 10 && ne(g) == 15
        @test isvalid_simplegraph(g)
        @test iscircularladdergraph(g)
        # tests for extreme values
        g = SG.circular_ladder_graph(3)
        @test nv(g) == 6 && ne(g) == 9
        @test iscircularladdergraph(g)
        g = SG.circular_ladder_graph(Int8(63))
        @test nv(g) == 126 && ne(g) == 189
        @test eltype(g) == Int8
        @test iscircularladdergraph(g)
        # tests for errors
        @test_throws InexactError SG.circular_ladder_graph(Int8(64))
        @test_throws DomainError SG.circular_ladder_graph(-1)
        @test_throws DomainError SG.circular_ladder_graph(0)
        @test_throws DomainError SG.circular_ladder_graph(1)
        @test_throws DomainError SG.circular_ladder_graph(2)
    end

    # checking that the nodes are organized correctly
    # see the docstring implementation notes for lollipop_graph
    function isbarbellgraph(g, n1, n2)
        nv(g) != n1 + n2 && return false
        ne(g) != n1 * (n1 - 1) ÷ 2 + n2 * (n2 - 1) ÷2 +1 && return false
        for i in 1:n1
            for j in (i + 1):n1
                !has_edge(g, i, j) && return false
            end
        end

        for i in n1 .+ 1:n2
            for j in (i+1):(n1+n2)
                !has_edge(g, i, j) && return false
            end
        end

        !has_edge(g, n1, n1+1) && return false
        return true
    end

    @testset "Barbell Graphs" begin
        g = @inferred(SG.barbell_graph(5, 6))
        @test nv(g) == 11 && ne(g) == 26
        @test isvalid_simplegraph(g)
        @test isbarbellgraph(g, 5, 6)
        g = SG.barbell_graph(Int8(5), Int8(6))
        @test nv(g) == 11 && ne(g) == 26
        @test isvalid_simplegraph(g)
        @test isbarbellgraph(g, 5, 6)
        # extreme values
        g = SG.barbell_graph(1, 5)
        @test nv(g) == 6 && ne(g) == 11
        @test isbarbellgraph(g, 1, 5)
        g = SG.barbell_graph(5, 1)
        @test nv(g) == 6 && ne(g) == 11
        @test isbarbellgraph(g, 5, 1)
        g = SG.barbell_graph(1, 1)
        @test nv(g) == 2 && ne(g) == 1
        @test isbarbellgraph(g, 1, 1)
        @test_throws OverflowError SG.barbell_graph(Int8(100), Int8(50))
        @test_throws DomainError SG.barbell_graph(1, 0)
        @test_throws DomainError SG.barbell_graph(0, 1)
        @test_throws DomainError SG.barbell_graph(-1, -1)
    end

    # checking that the nodes are organized correctly
    # see the docstring implementation notes for lollipop_graph
    function islollipopgraph(g, n1, n2)
        nv(g) != n1+n2 && return false
        ne(g) != n1*(n1-1)÷2+n2 && return false
        for i in 1:n1
            for j in (i+1):n1
                !has_edge(g, i, j) && return false
            end
        end

        for i in n1 .+ 1:(n2-1)
            !has_edge(g, i, i+1) && return false
        end

        !has_edge(g, n1, n1+1) && return false

        return true
    end

    @testset "Lollipop Graphs" begin
        g = @inferred(SG.lollipop_graph(3, 5))
        @test nv(g) == 8 && ne(g) == 8
        @test isvalid_simplegraph(g)
        @test islollipopgraph(g, 3, 5)
        g = SG.lollipop_graph(Int8(7), Int8(6))
        @test nv(g) == 13 && ne(g) == 27
        @test isvalid_simplegraph(g)
        @test islollipopgraph(g, 7, 6)
        # extreme values
        g = SG.lollipop_graph(1, 3)
        @test nv(g) == 4 && ne(g) == 3
        @test islollipopgraph(g, 1, 3)
        g = SG.lollipop_graph(3, 1)
        @test nv(g) == 4 && ne(g) == 4
        @test islollipopgraph(g, 3, 1)
        g = SG.lollipop_graph(1, 1)
        @test nv(g) == 2 && ne(g) == 1
        @test islollipopgraph(g, 1, 1)
        @test_throws OverflowError SG.lollipop_graph(Int8(100), Int8(50))
        @test_throws DomainError SG.lollipop_graph(1, 0)
        @test_throws DomainError SG.lollipop_graph(0, 1)
        @test_throws DomainError SG.lollipop_graph(-1, -1)
    end

    # checking if edgeset of g is equal to edges
    function isEdgeSet(g, edges)
        ne(g) != length(edges) && return false

        for (i, j) in edges
            !has_edge(g, i, j) && return false
        end

        return true
    end

    @testset "Circulant Graphs" begin
        # point graph
        g = @inferred(SG.circulant_graph(1, Vector{Int64}()))
        @test nv(g) == 1 && ne(g) == 0
        # path graph
        g = SG.circulant_graph(2, [1])
        @test nv(g) == 2 && ne(g) == 1
        # triangle graph
        g = SG.circulant_graph(3, [1])
        @test nv(g) == 3 && ne(g) == 3
        @test isEdgeSet(g, [(1, 2), (1, 3), (2, 3)])
        # tetrahedral graph
        @test SG.circulant_graph(4, [1, 2]) == SG.complete_graph(4)
        # utility graph
        g = SG.circulant_graph(6, [1, 3])
        @test nv(g) == 6 && ne(g) == 9
        @test isEdgeSet(g, [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (1, 6), (1, 4), (2, 5), (3, 6)])
        @test_throws DomainError SG.circulant_graph(0, [1, 2])
    end

    @testset "Circulant DiGraphs" begin
        # point graph
        g = @inferred(SG.circulant_digraph(1, Vector{Int64}()))
        @test nv(g) == 1 && ne(g) == 0
        # path graph
        g = SG.circulant_digraph(2, [1])
        @test nv(g) == 2 && ne(g) == 2
        @test isEdgeSet(g, [(1, 2), (2, 1)])
        # triangle graph
        g = SG.circulant_digraph(3, [1])
        @test nv(g) == 3 && ne(g) == 3
        @test isEdgeSet(g, [(1, 2), (2, 3), (3, 1)])
        # utility graph
        g = SG.circulant_digraph(6, [1, 3])
        @test nv(g) == 6 && ne(g) == 12
        @test isEdgeSet(g, [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 1), (1, 4), (4, 1), (2, 5), (3, 6), (5, 2), (6, 3)])
        @test_throws DomainError SG.circulant_digraph(0, [1, 2])
    end

    @testset "Friendship Graphs" begin
        # the friendship graph is a connected graph consisting of n cycles of length 3 sharing a common vertex
        for n in [10, 15, 20, 0x0a, 0x0f, 0x14]
            g = SG.friendship_graph(n)
            @test eltype(g) == eltype(n)
            @test !has_self_loops(g)
            @test !is_directed(g)
            @test degree(g, 1) == 2 * n
            @test nv(g) == 2 * n + 1
            for v in 2:nv(g)
                @test degree(g, v) == 2
            end
        end

        for n in [-5, 0]
            g = SG.friendship_graph(n)
            @test nv(g) == 1
        end
    end 
end
